/*
 *  Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved.
 *
 *  Hierarchical memory allocator, 1.2.1
 *  http://swapped.cc/halloc
 */

/*
 *  The program is distributed under terms of BSD license.
 *  You can obtain the copy of the license by visiting:
 *
 *  http://www.opensource.org/licenses/bsd-license.php
 */

#include <stdlib.h>  /* realloc */
#include <string.h>  /* memset & co */

#include "halloc.h"
#include "align.h"
#include "hlist.h"

/*
 *  block control header
 */
typedef struct hblock
{
#ifndef NDEBUG
#define HH_MAGIC    0x20040518L
    long          magic;
#endif
    hlist_item_t  siblings; /* 2 pointers */
    hlist_head_t  children; /* 1 pointer  */
    max_align_t   data[1];  /* not allocated, see below */

} hblock_t;

#define sizeof_hblock offsetof(hblock_t, data)

/*
 *
 */
realloc_t halloc_allocator = NULL;

#define allocator halloc_allocator

/*
 *  static methods
 */
static void _set_allocator(void);
static void *_realloc(void *ptr, size_t n);

static int  _relate(hblock_t *b, hblock_t *p);
static void _free_children(hblock_t *p);

/*
 *  Core API
 */
void *halloc(void *ptr, size_t len)
{
    hblock_t *p;

    /* set up default allocator */
    if (! allocator)
    {
        _set_allocator();
        assert(allocator);
    }

    /* calloc */
    if (! ptr)
    {
        if (! len)
            return NULL;

        p = allocator(0, len + sizeof_hblock);

        if (! p)
            return NULL;

#ifndef NDEBUG
        p->magic = HH_MAGIC;
#endif
        hlist_init(&p->children);
        hlist_init_item(&p->siblings);

        return p->data;
    }

    p = structof(ptr, hblock_t, data);
    assert(p->magic == HH_MAGIC);

    /* realloc */
    if (len)
    {
        p = allocator(p, len + sizeof_hblock);

        if (! p)
            return NULL;

        hlist_relink(&p->siblings);
        hlist_relink_head(&p->children);

        return p->data;
    }

    /* free */
    _free_children(p);
    hlist_del(&p->siblings);
    allocator(p, 0);

    return NULL;
}

void hattach(void *block, void *parent)
{
    hblock_t *b, * p;

    if (! block)
    {
        assert(! parent);
        return;
    }

    /* detach */
    b = structof(block, hblock_t, data);
    assert(b->magic == HH_MAGIC);

    hlist_del(&b->siblings);

    if (! parent)
        return;

    /* attach */
    p = structof(parent, hblock_t, data);
    assert(p->magic == HH_MAGIC);

    /* sanity checks */
    assert(b != p);          /* trivial */
    assert(! _relate(p, b)); /* heavy ! */

    hlist_add(&p->children, &b->siblings);
}

/*
 *  malloc/free api
 */
void *h_malloc(size_t len)
{
    return halloc(0, len);
}

void *h_calloc(size_t n, size_t len)
{
    void *ptr = halloc(0, len *= n);
    return ptr ? memset(ptr, 0, len) : NULL;
}

void *h_realloc(void *ptr, size_t len)
{
    return halloc(ptr, len);
}

void   h_free(void *ptr)
{
    halloc(ptr, 0);
}

char *h_strdup(const char *str)
{
    size_t len = strlen(str);
    char *ptr = halloc(0, len + 1);
    return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
}

/*
 *  static stuff
 */
static void _set_allocator(void)
{
    void *p;
    assert(! allocator);

    /*
     *  the purpose of the test below is to check the behaviour
     *  of realloc(ptr, 0), which is defined in the standard
     *  as an implementation-specific. if it returns zero,
     *  then it's equivalent to free(). it can however return
     *  non-zero, in which case it cannot be used for freeing
     *  memory blocks and we'll need to supply our own version
     *
     *  Thanks to Stan Tobias for pointing this tricky part out.
     */
    allocator = realloc;

    if (!(p = malloc(1)))
        /* hmm */
        return;

    if ((p = realloc(p, 0)))
    {
        /* realloc cannot be used as free() */
        allocator = _realloc;
        free(p);
    }
}

static void *_realloc(void *ptr, size_t n)
{
    /*
     *  free'ing realloc()
     */
    if (n)
        return realloc(ptr, n);

    free(ptr);
    return NULL;
}

static int _relate(hblock_t *b, hblock_t *p)
{
    hlist_item_t *i;

    if (!b || !p)
        return 0;

    /*
     *  since there is no 'parent' pointer, which would've allowed
     *  O(log(n)) upward traversal, the check must use O(n) downward
     *  iteration of the entire hierarchy; and this can be VERY SLOW
     */
    hlist_for_each(i, &p->children)
    {
        hblock_t *q = structof(i, hblock_t, siblings);

        if (q == b || _relate(b, q))
            return 1;
    }
    return 0;
}

static void _free_children(hblock_t *p)
{
    hlist_item_t *i, * tmp;

#ifndef NDEBUG
    /*
     *  this catches loops in hierarchy with almost zero
     *  overhead (compared to _relate() running time)
     */
    assert(p && p->magic == HH_MAGIC);
    p->magic = 0;
#endif
    hlist_for_each_safe(i, tmp, &p->children)
    {
        hblock_t *q = structof(i, hblock_t, siblings);
        _free_children(q);
        allocator(q, 0);
    }
}

